A computer network, in the present sense, is a network of packet forwarding stations (nodes) by means of which various packet originating and receiving stations (commonly termed host computers, or just hosts) are interconnected. Messages are originated and received by the hosts; the role of the network is to route them between the hosts. A node is generally connected to several others. Each node has an input module for each host and each other node it is connected to, and means for inspecting each incoming packet, to determine which node or host it should forward the packet to. (For present purposes, we need not distinguish between "messages" and "packets".)
A packet consists of a header containing control data, and a body containing the information which is being passed from the originating host to the destination host. The header contains the destination of the packet and various other fields, some of which are modified as the packet passes through the network.
When the packet is received at a node, it is temporarily stored in the node, which inspects the address field of the packet to determine which link it should go out on, and in due course transmits the packet on that link.
The node may conveniently contain a packet memory for the incoming packets and a plurality of output modules, one for each link to other nodes or hosts. A pointer to the location of the incoming packet in the packet memory is passed to the output module of the appropriate link, the pointers of the various packets to be transmitted on that link are queued, and the packets are transmitted in the sequence of the pointers in the queue.
Many computer networks incorporate means for limiting the life of packets in the network. There are various reasons for this; for example, a packet may be held up in the network for a time which is comparable to a typical time-out and resend time of the hosts, the packet may be undeliverable, or there may be a fault in the network which results in the packet circulating round a loop.
One way of limiting the life of a packet is to include in each packet a hop count which is set to some suitable value when the packet is originated (either by the host or on entering the network from the host) and decremented each time the packet passes from one node to the next, the packet being destroyed if its hop count reaches 0. (This way of measuring the life of a packet is of course related somewhat loosely to the chronological age of the packet.)
Another way of limiting the life of a packet is to monitor, in some way, the time for which it exists, and destroy it if it exceeds a predetermined age. The "destruction" of a packet usually involves discarding any references to it and marking the memory space which it occupies as free (so that other packets can be stored in that space).
This can be done by a birthtime technique; including in each packet the time at which it was born. Determining the age of the packet then involves subtracting the time of birth of the packet from the current time, which involves having a system-wide clock. This involves synchronizing clocks in all nodes, which is not always feasible, particularly if the network is large and different parts are under different managements and/or of different designs.
An alternative way of monitoring the time for which a packet exists is the lifetime technique; including in each packet a lifetime which is included in the packet when it is born and which is decremented each time the packet passes through a node by the time which the packet spends in that node. This technique overcomes the synchronization problems of the birthtime technique.
In practice, the time the packet spends in a node is measured in units of predetermined length, and the packet is assumed to spend a minimum of i unit in a node. The time for which a packet exists, measured in this way, is, of course not identical to the chronological age of the packet. One reason for this is the quantization of the time units just mentioned. Another is the problem of accounting for the transmission time between nodes, as it may not be feasible to measure this without synchronization. The time measured in this way is however an adequate approximation to the chronological age of the packet.
In the lifetime technique, one of the fields in the packet header is an age field containing the remaining part of the lifetime of the packet. This is stored, along with the rest of the packet, in the packet memory when the packet is received at the node. When the packet is retrieved from the node for transmission, the age field has to be decremented by the time which the packet has spent in the node. This time is determined by determining the difference between the times at which the packet enters and leaves the node. This requires the time at which the packet enters the node to be recorded, so that it is available when the packet reaches the top of the queue in the output module.
There is no difficulty in principle in doing this. However, in practice this imposes a heavy load on the node; the burden arises largely because the number of packets which may accumulate in a node is large.
The packet arrival time can be stored in the output module, associated with the pointer to the packet itself (which is in the packet memory). However, the pointer and other associated information will generally be only a few words long. This size will have to be increased by a substantial amount to accommodate the packet arrival time as well. The storage capacity of each output module, which will usually have to be fast memory, must therefore be significantly increased.
The packet arrival time can alternatively be stored in the packet memory, along with the packet itself. The packet will usually be very much longer than the packet arrival time field, so although the size of the packet memory has to be increased, this is not an excessive burden. However, the packet memory is normally optimized for serial access. That is, it is designed so that it is fast for reading from or writing into a long sequence of successive memory locations. A packet arrival time will typically be only a few words long, so retrieving packet arrival times will be much closer to random access than serial access for such a memory. The mean speed (bandwidth capacity)of the packet memory is therefore reduced substantially.
In systems in which the nodes have a high through-put, the lifetime technique thus imposes a heavy storage and processing burden on the nodes. In fact, in one commercial system in which the lifetime technique was used, its drawbacks were found to be so severe that the system was modified to use the hop count technique instead.
It is possible to reduce the amount of storage required for the lifetime technique, by storing only the remaining lifetime of the packet and decrementing it on every time unit. However, this obviously imposes a severe processing load, since the lifetime field of every packet in the node has to be read from whatever memory it is stored in, decremented, and written back into memory on every time unit.
The object of the present invention is to provide an implementation of the lifetime technique which substantially reduces the storage and processing burden on the nodes.